package algorithm.sorting;

import java.util.Arrays;

/**
 * 快速排序
 * 长度划分尽量接近
 * 建议使用栈
 */
public class QuickSort {
    public static void main(String[] args) {
        //int[] table = {38,26,97,19,66,1,5,49};
        int[] table = {38,26,97,19,66,1,5,49,1,2,3,5,2,3};
        quickSort(table);
        System.out.println(Arrays.toString(table));
    }
    public static void quickSort(int[] table) {
        quickSort(table,0,table.length-1);
    }
    //递归算法,low、high为上下界
    public static void quickSort(int[] table, int low, int high) {
        if (low < high){
            int i=low,j=high;
            int vot = table[i];//第一个值作为基准值
            while (i!=j){
                while (i<j && vot<=table[j]){ //从后向前寻找最小值
                    j--;
                }
                if(i<j){
                    table[i] = table[j]; //较小元素想前移
                    i++;
                }
                while(i<j && table[i]<vot){//从前向后寻找最大值
                    i++;
                }
                if(i<j){
                    table[j] = table[i]; //较大元素向后移
                    j--;
                }
            }
            table[i] = vot;
            //System.out.println(low+".."+high+",vot="+vot+" ");
            //System.out.println(Arrays.toString(table));
            quickSort(table,low,j-1); //前端再排
            quickSort(table,i+1,high);//后端再排
        }
    }
}
